// https://leetcode.cn/problems/shortest-subarray-with-sum-at-least-k/
// Created by ade on 2022/10/26.
//
#include <vector>
#include <iostream>
#include <deque>

using namespace std;

class Solution {
public:
    int shortestSubarray(vector<int> &nums, int k) {
        int len = nums.size();
        vector<long> preSum(len + 1);
        deque<int> d = {0};
        for (int i = 1; i <= len; i++)
            preSum[i] = preSum[i - 1] + nums[i - 1];
        int minI = len + 1;
        // 这种情况主要是处理长度为1的情况
        for (int i = 1; i <= len; i++) {
            while (!d.empty() && preSum[i] - preSum[d.front()] >= k) {
                minI = min(minI, i - d.front());
                d.pop_front();
            }
            while (!d.empty() && preSum[d.back()] >= preSum[i])
                d.pop_back();
            d.push_back(i);
        }
        return minI == len + 1 ? -1 : minI;
        /*int n = nums.size();
        vector<long> preSumArr(n + 1);
        for (int i = 0; i < n; i++) {
            preSumArr[i + 1] = preSumArr[i] + nums[i];
        }
        int res = n + 1;
        deque<int> qu;
        for (int i = 0; i <= n; i++) {
            long curSum = preSumArr[i];
            while (!qu.empty() && curSum - preSumArr[qu.front()] >= k) {
                res = min(res, i - qu.front());
                cout << "i:" << i << ",front:" << qu.front() << ",sum:" << curSum - preSumArr[qu.front()] << endl;
                qu.pop_front();
            }
            while (!qu.empty() && preSumArr[qu.back()] >= curSum) {
                qu.pop_back();
            }
            qu.push_back(i);
        }
        return res < n + 1 ? res : -1;*/
    }
};

int main() {
    Solution so;
    vector<int> nums = {84, -37, 32, 40, 95};
    cout << so.shortestSubarray(nums, 167);
    return 0;
}
